package Algorithm.dynamicProgramming.introduct;

/**
 * 376. 摆动序列 https://leetcode.cn/problems/wiggle-subsequence/description/
 * 题目简述：求一个数组中作为 摆动序列 的 最长子序列的长度
 */
public class WiggleMaxLength {

    public static void main(String[] args) {
        new WiggleMaxLength().wiggleMaxLength(new int[]{1,2,3,4,5,6,7,8,9});
    }

    /**
     * 思路一：动态规划
     * 1. 定义dp：down[i]为前i+1个数的序列中 最后两个数字递减的最长摆动子序列的长度，
     *           up[i]为前i+1个数的序列中 最后两个数字递增的最长摆动子序列的长度。
     * 2. 状态转移方程：若nums[i] > nums[i-1]即递增，则down[i] = down[i-1]， up[i] = down[i-1]+1
     *               若nums[i] < nums[i-1]即递减，则down[i] = up[i-1]+1， up[i] = up[i-1]
     * 3. 初始化：up[0] = 1;down[0] = 1;
     * 4. 递推完毕后结果即为 Math.max(up, down)
     * 参考：https://leetcode.cn/problems/wiggle-subsequence/solutions/284327/tan-xin-si-lu-qing-xi-er-zheng-que-de-ti-jie-by-lg/
     */
    public int wiggleMaxLength(int[] nums) {
        int up = 1, down = 1;
        for (int i = 1;i < nums.length;i++) {
            if (nums[i] > nums[i-1])
                up = down + 1;
            else if (nums[i] < nums[i-1]) {
                down = up + 1;
            }
        }
        return Math.max(up, down);
    }

    /**
     * 思路二：一次摆动就是一个峰，本质就是求有几个最值，左端点是一个最值，之后每次单调趋势的改变都会产生一个最值
     */
    public int wiggleMaxLength2(int[] nums) {
        int len = nums.length;
        boolean isUp = false;
        //左端点是一个最值，初始a=1
        int a=1, i = 1;
        //先确认最开始的趋势
        for (;i < len;i++) {
            if (nums[i] != nums[i-1]) {
                //趋势改变，最值数增1
                isUp = nums[i] > nums[i-1];
                a++;
                break;
            }
        }
        //之后每次趋势的改变都会增加一个最值（新趋势右端）
        for(;i < len;i++) {
            if(isUp && nums[i] < nums[i-1]) {
                a++;
                isUp = false;
            } else if(!isUp && nums[i] > nums[i-1]) {
                a++;
                isUp = true;
            }
        }
        return a;
    }
}
